/* 构造队列结构
* 225. 用队列实现栈
*/
#define LEN 100
typedef struct queue {
    int* data;
    int head;
    int rear; //后部
    int size; //空间大小
    int used; 
} Queue;

/* 初始化队列 */
Queue* initQueue(int length) {
    Queue* obj = (Queue*)malloc(sizeof(Queue));
    obj->data = (int*)malloc(sizeof(int) * length);
    obj->head = 0;
    obj->rear = 0;
    obj->size = length;
    obj->used = 0;
    return obj;
}

/* 入队列操作 */
void enQueue(Queue* obj, int e) {
    obj->used ++;
    obj->data[obj->rear] = e;
    obj->rear = (obj->rear + 1) % obj->size;
}

/* 出队列操作 */
int deQueue(Queue* obj) {
    obj->used --;
    /* 将队列头部元素记录下来 */
    int a = obj->data[obj->head];
    /* 队列不止一个元素，将头部后移一位即可 */
    obj->head = (obj->head + 1) % obj->size;
    return a;
}

/* 判断队列是否为空 */
bool isEmpty(Queue* obj) {
    return obj->used == 0;
}

/* 栈为两个队列模拟 */
typedef struct {
    Queue *stack, *help;
} MyStack;

/** Initialize your data structure here. */
MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    obj->stack = initQueue(LEN);
    obj->help = initQueue(LEN);
    return obj;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    enQueue(obj->stack, x);
}
void swap(Queue** a, Queue** b)
{
    Queue* tmp = *a;
    *a = *b;
    *b = tmp;
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    while(obj->stack->used > 1) {
        enQueue(obj->help, deQueue(obj->stack));
    }
    int tmp = deQueue(obj->stack);
    swap(&obj->stack, &obj->help);  // 即使是结构体的指针，要交换也得传指向它的指针
    return tmp;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    while(obj->stack->used > 1) {
        enQueue(obj->help, deQueue(obj->stack));
    }
    int tmp = deQueue(obj->stack);
    enQueue(obj->help, tmp);
    swap(&obj->stack, &obj->help);
    return tmp;
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    if (obj->stack->used == 0 && obj->help->used == 0) {
        return true;
    }
    return false;
}

void myStackFree(MyStack* obj) {
    free(obj->stack->data);
    obj->stack->data = NULL;
    free(obj->stack);
    obj->stack = NULL;
    free(obj->help->data);
    obj->help->data = NULL;
    free(obj->help);
    obj->help = NULL;
    free(obj);
    obj = NULL;
}
